package practice1_100;

public class Practice111 {
    //这题很贼，最小深度是指，真正叶子节点，[2,null,3,null,4,null,5,null,6]譬如这种他的最小深度就是5，而不是1

    /**
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        //节点为空，返回0
        if(root==null) return 0;
        return dp(root.left,root.right)+1;
    }
    public int dp(TreeNode left,TreeNode right){
        //左叶子为空，只考虑右叶子的长度
        if(left==null&&right!=null){
            return Math.min(dp(right.left,right.right)+1,Integer.MAX_VALUE);
        }else if(left!=null&&right==null){        //右孩子为空，只考虑左孩子的长度
            return Math.min(dp(left.left,left.right)+1,Integer.MAX_VALUE);
        }else if(left==null&&right==null) {//全空则返回0
            return 0;
        }else {//都不为空才考虑两边比较长短
            return Math.min(dp(left.left,left.right)+1,dp(right.left,right.right)+1);
        }
    }
}
